In circuit simulation of very large circuits, i.e. of circuits having a great plurality of elements, a serial processing, i.e. the determination of the circuit quantities by a computer, is extremely time-consuming. Even vector computers that are very expensive in terms of operation have an immense need of calculating capacity and time for determining the electrical descriptive quantities for a circuit that comprises a few 100,000 transistors.
In order to avoid the serial implementation of a circuit simulation for this reason, the electrical circuit can be divided into a plurality of parts that are then respectively processed by different computers or, respectively, processors, this leading to a parallel implementation of the circuit simulation.
In order, however, to achieve an optimally good parallelization of the determination of the electrical descriptive quantities for the electric circuit, it is advantageous to consider the following two criteria in the partitioning of the electrical circuit into a plurality of parts. First, it is of considerable significance that all partitions of the electrical circuit that are formed are of the same size insofar as possible, in order to thereby intensify the effect that can be achieved by the parallelization. When, for example, one partition is orders of magnitude larger than the remaining partitions, then the processing of the significantly larger partition is in turn far more calculation-consuming then the processing of the remaining partitions. Second, it is important in the partitioning that only a slight plurality of connections exists between the individual partitions insofar as possible since, in known methods for “parallelized” circuit simulation, the required transmission capacity, i.e. the required communication between the computers or, respectively, processors that respectively process one partition, increases substantially with an increasing number of existing connections between the partitions.
A language for the textual description of an electrical circuit that can be processed by a computer is the circuit simulation language SPICE See I Hoefer, et al., SPICE Analyseprogramm fur electronische Schaltungen, Springer, Berlin (1985), pp. 7–22.
U. Kleis, et al., Doman Decomposition Methods for Circuit Simulation, Proceedings of the 8th Workshop on Parallel and Distributed Simulation, PADS, Edinburgh, UK (July, 1994), pp. 183–86, and U. Wever, et al., Parallel Transient Analysis for Circuit Simulation, Proceedings of the 29th Annual Hawaii International Conference on System Sciences (1946), pp. 442–47 describe how a parallelized circuit simulation can be implemented, assuming an arbitrary number of partitions of the electrical circuit exist. The way in which the partitions can be determined is not described in these documents.
B. Riess, Partitioning Very Large Circuits Using Analytical Placement Techniques, Proceedings of the 31st ACM/IEEE Design Automation Conference (1994), pp. 646–51 discloses a global partitioning method on what is referred logic level, which is also referred to as gate level.
Discrete events are described on the logic level, but no steady dynamic property of an electrical circuit on what is referred to as the transistor level, i.e. on the actual physical level of the electrical circuit, can be described with these.
The results of a circuit simulation that ensues on the logic level is thus unreliable and imprecise for certain applications since an exact time course of the electrical signals that occur in the electrical circuit cannot be taken into consideration.
Further, a description of the individual gates is required for the circuit simulation, this having to be determined first before the method can be implemented.
An overview of various partitioning rules can be found in P. Johannes, Partitioning of VLSI Circuits and Systems, 33rd Design and Automation Conference, Las Vegas (Jun. 3–7, 1996), pp. 83–87.
A parallelized method for clustering an electrical circuit according to what is referred to as the bottom-up principle is disclosed by J. Cong, et al., A Parallel Bottom-Up Clustering Algorithm with Applications to Circuit Partitioning in VLSI Design, 30th ACM/IEEE Design Automation Conference, Jun. 14–18, 1993, pp. 755–760.